package com.leetcode.partition1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/8/15 10:16
 */
public class LC51N皇后 {

    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> answer = new ArrayList<>();
        char[][] chessboard = new char[n][n];
        for (char[] chess : chessboard) {
            Arrays.fill(chess, '.');
        }
        backtracking(answer, n, 0, chessboard);
        return answer;
    }

    public static void main(String[] args) {
        List<List<String>> answer = solveNQueens(8);
        for (List<String> ans : answer) {
            for (String item : ans) {
                System.out.println(item);
            }
            System.out.println("-----------------");
        }
        System.out.println(answer.size());
    }

    private static void backtracking(List<List<String>> answer, int n, int row, char[][] chessboard) {
        if (row == n) {
            //将当前棋盘的状态存放
            List<String> ans = new ArrayList<>(n);
            for (char[] chessRow : chessboard) {
                ans.add(new String(chessRow));
            }
            answer.add(ans);
            return;
        }
        //由参数row控制行，递归的深度，由col控制列
        for (int col = 0; col < n; col++) {
            if (isValid(row, col, chessboard, n)) {
                //当前位置合法就可以放置皇后
                chessboard[row][col] = 'Q';
                backtracking(answer, n, row + 1, chessboard);
                //回溯撤销皇后
                chessboard[row][col] = '.';
            }
        }
    }

    private static boolean isValid(int row, int col, char[][] chessboard, int n) {
        // 检查列
        for (int i = 0; i < row; i++) { // 这是⼀个剪枝
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }
        // 检查 45度⻆是否有皇后
        for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        // 检查 135度⻆是否有皇后
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}
